package airthmetic.exercise.dp;

public class DPDemo {

    // leetCode 198. 打家劫舍
    public static int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return nums[0] > nums[1] ? nums[0] : nums[1];
        }

        int length = nums.length;
        int[] newArr = new int[length + 1];
        newArr[0] = 0;
        newArr[1] = nums[0];

        for (int i = 2; i <= length; i++) {
            newArr[i] = Math.max(newArr[i - 1], (newArr[i - 2] + nums[i - 1]));
        }
        return newArr[length];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 7, 1, 2, 2, 3, 4, 1, 7};
        System.out.println(rob(arr));
    }
}
